DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2022.12

Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

Authors: David Auger, Pierre Coucheney, and Loric Duhazé

Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)

Abstract

A rotor walk in a directed graph can be thought of as a deterministic version of a Markov Chain, where a pebble moves from vertex to vertex following a simple rule until a terminal vertex, or sink, has been reached. The ARRIVAL problem, as defined by Dohrau et al. [Dohrau et al., 2017], consists in determining which sink will be reached. While the walk itself can take an exponential number of steps, this problem belongs to the complexity class NP ∩ co-NP without being known to be in P. In this work, we define a class of directed graphs, namely tree-like multigraphs, which are multigraphs having the global shape of an undirected tree. We prove that in this class, ARRIVAL can be solved in almost linear time, while the number of steps of a rotor walk can still be exponential. Then, we give an application of this result to solve some deterministic analogs of stochastic models (e.g., Markovian decision processes, Stochastic Games).

Cite as

David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 12:1-12:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.MFCS.2022.12,
  author =	{Auger, David and Coucheney, Pierre and Duhaz\'{e}, Loric},
  title =	{{Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{12:1--12:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.12},
  URN =		{urn:nbn:de:0030-drops-168103},
  doi =		{10.4230/LIPIcs.MFCS.2022.12},
  annote =	{Keywords: Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like Multigraph}
}

Document

DOI: 10.4230/LIPIcs.STACS.2019.9

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule

Authors: David Auger, Pierre Coucheney, and Yann Strozecki

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract

The best algorithm so far for solving Simple Stochastic Games is Ludwig’s randomized algorithm [Ludwig, 1995] which works in expected 2^{O(sqrt{n})} time. We first give a simpler iterative variant of this algorithm, using Bland’s rule from the simplex algorithm, which uses exponentially less random bits than Ludwig’s version. Then, we show how to adapt this method to the algorithm of Gimbert and Horn [Gimbert and Horn, 2008] whose worst case complexity is O(k!), where k is the number of random nodes. Our algorithm has an expected running time of 2^{O(k)}, and works for general random nodes with arbitrary outdegree and probability distribution on outgoing arcs.

Cite as

David Auger, Pierre Coucheney, and Yann Strozecki. Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{auger_et_al:LIPIcs.STACS.2019.9,
  author =	{Auger, David and Coucheney, Pierre and Strozecki, Yann},
  title =	{{Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.9},
  URN =		{urn:nbn:de:0030-drops-102488},
  doi =		{10.4230/LIPIcs.STACS.2019.9},
  annote =	{Keywords: simple stochastic games, randomized algorithm, parametrized complexity, strategy improvement, Bland’s rule}
}

Search Results

Documents authored by Coucheney, Pierre

Polynomial Time Algorithm for ARRIVAL on Tree-Like Multigraphs

Abstract

Cite as

Solving Simple Stochastic Games with Few Random Nodes Faster Using Bland’s Rule

Abstract

Cite as

Thanks for your feedback!

Could not send message